#pragma once
#include<assert.h>
#include <iostream>
using namespace std;

enum Colour
{
	RED,
	BLACK,
};

//节点
template<class T>
struct RBTreeNode
{
	RBTreeNode(const T& data = T())
		: _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _data(data)
		, _color(RED)
	{}

	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;
	T _data;
	Colour _color;
};
//////////////////////////////////////////////////////

//迭代器
template<class T, class Ref, class Ptr>
struct __RBTree_Iterator
{
	typedef RBTreeNode<T> Node;
	typedef __RBTree_Iterator< T, Ref, Ptr> Self;
	Node* _node;

	//构造函数(使用节点构造迭代器)
	__RBTree_Iterator(Node* node)
		:_node(node)
	{}

	//1.typedef __RBTree_Iterator<T, T&, T*>  iterator;  --->拷贝构造
	//2.typedef __RBTree_Iterator<T, const T&, const T*>  const_iterator;
	//  --->支持普通迭代器到const迭代器的转换
	__RBTree_Iterator(const __RBTree_Iterator<T, T&, T*>& it)
		:_node(it._node)
	{}

	//相关功能
	Ref operator*()
	{
		return _node->_data;
	}

	Ptr operator->()
	{
		return &_node->_data;
	}

	bool operator!=(const Self& s)
	{
		return _node != s._node;
	}

	Self& operator++()
	{
		//1.右子树不为空,找右子树的最左节点
		if (_node->_right)
		{
			Node* subRL = _node->_right;
			while (subRL->_left)
			{
				subRL = subRL->_left;
			}
			_node = subRL;
		}
		//2.右子树为空, 找节点是父亲左孩子的祖先
		else
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && parent->_right == cur)
			{
				cur = parent;
				parent = parent->_parent;
			}
			_node = parent;
		}

		return *this;
	}

	Self& operator--()
	{
		//1.如果有左子树,就往左子树走,找其最右边的节点
		if (_node->_left)
		{
			Node* subLR = _node->_left;
			while (subLR->_right)
			{
				subLR = subLR->_right;
			}
			//然后把这个节点给it
			_node = subLR;
		}
		//2.如果没有左子树, 就找节点是父亲右孩子的祖先
		else
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && parent->_left == cur)
			{
				cur = parent;
				parent = parent->_parent;
			}
			//然后把这个节点给it
			_node = parent;
		}

		return *this;
	}
};

////////////////////////////////////////////////////////////////////////

template<class K, class T, class KeyOfT>
class RBTree
{
	typedef RBTreeNode<T> Node;
public:
	//析构函数
	~RBTree()
	{
		destory(_root);
		_root = nullptr;
	}

	//迭代器
	typedef __RBTree_Iterator<T, T&, T*>  iterator;
	typedef __RBTree_Iterator<T, const T&, const T*>  const_iterator;

	iterator begin()
	{
		//返回最左边的节点
		Node* cur = _root;
		while (cur && cur->_left)
		{
			cur = cur->_left;
		}
		return iterator(cur);
	}

	iterator end()
	{
		//返回最右边节点的下一个节点
		return iterator(nullptr);
	}

	//const迭代器
	const_iterator begin() const
	{
		//返回最左边的节点
		Node* cur = _root;
		while (cur && cur->_left)
		{
			cur = cur->_left;
		}
		return const_iterator(cur);
	}

	const_iterator end()const
	{
		//返回最右边节点的下一个节点
		return const_iterator(nullptr);
	}


	//1.插入
	pair<iterator, bool> Insert(const T& data)
	{
		KeyOfT kot;
		//空树
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_color = BLACK;
			return make_pair(iterator(_root), true);
		}
		//非空树
		//1.找到插入的位置
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (kot(cur->_data) > kot(data))
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (kot(cur->_data) < kot(data))
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return make_pair(iterator(cur), false);
			}
		}
		//2.生成节点, 并链接节点
		cur = new Node(data);
		Node* newnode = cur;
		if (kot(parent->_data) > kot(data))
		{
			parent->_left = cur;
		}
		else if (kot(parent->_data) < kot(data))
		{
			parent->_right = cur;
		}
		cur->_parent = parent;

		//3.判断是否需要调整红黑树
		//如果p红且存在,就需要调整(cur默认是红,出现连续的红色节点)
		//接下来对cur的位置进行讨论
		while (parent && parent->_color == RED)
		{
			Node* grandfather = parent->_parent;
			//讨论p的位置,是在g的左/g的右

			//p在g的左
			if (grandfather && grandfather->_left == parent)
			{
				Node* uncle = grandfather->_right;
				//情况1:p,u都为红,将p,u变黑,g变红,然后向上调整
				if (uncle && uncle->_color == RED)
				{
					parent->_color = BLACK;
					uncle->_color = BLACK;
					grandfather->_color = RED;
					//继续调整
					cur = grandfather;
					parent = cur->_parent;
				}
				//情况2:p红,u黑/u不在, 讨论cur的位置
				else
				{
					//       g
					//    p     u
					//  c
					//右单旋 + 变色
					if (parent->_left == cur)
					{
						RotateR(grandfather);
						grandfather->_color = RED;
						parent->_color = BLACK;
						break;
					}
					//       g
					//   p       u
					//      c
					//p左旋,g右旋 + 变色
					else
					{
						RotateL(parent);
						RotateR(grandfather);

						cur->_color = BLACK;
						grandfather->_color = RED;
						break;
					}
				}
			}
			//p在g的右
			else if (grandfather && grandfather->_right == parent)
			{
				Node* uncle = grandfather->_left;
				//情况1:p红,u红, 变色+调整
				if (uncle && uncle->_color == RED)
				{
					grandfather->_color = RED;
					parent->_color = BLACK;
					uncle->_color = BLACK;

					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					//情况2:p红,u黑/u不在,讨论cur的位置
					//      g
					//  u       p
					//              c
					//g左单旋
					if (cur == parent->_right)
					{
						RotateL(grandfather);
						grandfather->_color = RED;
						parent->_color = BLACK;
						break;
					}
					//      g
					//  u       p
					//        c
					//p右单旋, g左单旋 + 变色
					else
					{
						RotateR(parent);
						RotateL(grandfather);

						grandfather->_color = RED;
						cur->_color = BLACK;
						break;
					}
				}
			}
			//调整到根以后
			//最后把根节点变为红色
			_root->_color = BLACK;
		}

		return make_pair(iterator(newnode), true);
	}

	//////////////////////////////////////////////////////////////////////////////////////////////

	//2.查找
	Node* Find(const K& key)
	{
		KeyOfT kot;
		Node* cur = _root;
		while (cur)
		{
			//根据搜索二叉树性质来找这个节点
			if (kot(cur->_data) > key)
			{
				cur = cur->_left;
			}
			else if (kot(cur->_data) < key)
			{
				cur = cur->_right;
			}
			else
			{
				//找到了返回该节点
				return cur;
			}
		}
		//没找到返回空
		return nullptr;
	}

	//3.红黑树的检查
	bool Is_RBTree()
	{
		return _Is_RBTree(_root);
	}

	//4.中序遍历
	void Inorder()
	{
		_Inorder(_root);
		cout << endl;
	}

protected:
	//中序遍历
	void _Inorder(Node* root)
	{
		if (root == nullptr)
			return;

		_Inorder(root->_left);
		cout << root->_data << " ";
		_Inorder(root->_right);
	}

	//红黑树的检查
	bool _Is_RBTree(Node* root)
	{
		//规则2:根节点是黑色的
		if (root == nullptr) return true;
		if (root->_color != BLACK) return false;

		//规则3:不能有连续的红色节点
		//规则4:每条路径上的黑色节点个数相等
		Node* cur = root; int base_nums = 0;
		while (cur)
		{
			if (cur->_color == BLACK) base_nums++;
			cur = cur->_left;
		}
		Check(root, base_nums, 0);

	}

	bool Check(Node* root, int base_nums, int block_nums)
	{
		if (root == nullptr)
		{
			if (base_nums != block_nums)
			{
				cout << "路径上的黑色节点个数不相同" << endl;
				return false;
			}
			return true;
		}

		//检查有没有连续的红色节点
		if (root->_parent && root->_color == RED && root->_parent->_color == RED)
		{
			cout << "有连续的红色节点" << endl;
			return false;
		}

		//遇到一个黑色节点就++
		if (root->_color == BLACK) block_nums++;

		return Check(root->_left, base_nums, block_nums)
			&& Check(root->_right, base_nums, block_nums);
	}

private:
	//左旋
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		Node* ppnode = parent->_parent;

		//左旋 + 链接节点
		if (subRL)
			subRL->_parent = parent;
		parent->_right = subRL;

		subR->_left = parent;
		parent->_parent = subR;

		if (parent == _root)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = subR;
			}
			else
			{
				ppnode->_right = subR;
			}
			subR->_parent = ppnode;
		}
	}

	//右旋
	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		Node* ppnode = parent->_parent;

		//右旋 + 链接节点
		if (subLR)
			subLR->_parent = parent;
		parent->_left = subLR;

		subL->_right = parent;
		parent->_parent = subL;

		if (parent == _root)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = subL;
			}
			else
			{
				ppnode->_right = subL;
			}
			subL->_parent = ppnode;
		}
	}

	//销毁树
	void destory(Node* root)
	{
		if (root == nullptr) return;

		destory(root->_left);
		destory(root->_right);
		delete root;
	}


private:
	Node* _root = nullptr;
};